Random Sampling

Sampling your environment at random might seem like a strange idea, but it's actually a relatively efficient way to build up a set of feasible states through your free space. In this exercise you'll implement random sampling of your 3D environment to generate candidate nodes for a graph representation of your state space.

The process you'll go through to generate a set of feasible states will be to first scatter points at random throughout your environment over some range in x, y, and z. Then for each of those points, you'll test whether it lies inside the ground plane polygon of any obstacles, and if so, whether or not it is above or below the height of the obstacle.

You'll then discard points that are in collision with obstacles, or in other words, those that lie within the ground plane polygon of an obstacle and below the height of that obstacle. And what you're left with are a collection of states that lie in the free space!

Python Shapely package

In this exercise, you'll leverage a powerful Python package called Shapely. With this package you can define a polygon object using a set of coordinates like this:

from shapely.geometry import Polygon
coords = [(0, 0), (1, 0), (1, 1), (0, 1)]
poly = Polygon(coords)

You now have a polygon object with various attributes

print(poly.area)
print(poly.length)
print(poly.bounds)
> 1.0
> 4.0
> (0.0, 0.0, 1.0, 1.0)

But more importantly, for our purposes here you can define a point using Shapely as well and then test whether that point lies within the polygon:

from shapely.geometry import Point
p1 = Point(0.5, 0.5)
p2 = Point(1.5, 1.5)
print(poly.contains(p1))
print(poly.contains(p2))
> True
> False

And simple as that you have a method for testing whether a point lies within the ground plane polygon of an obstacle! All you need to do is add in a check for height and you've got your random sampling test in order.

Random Sampling Exercise

In this exercise you'll read in the same colliders.csv file you've been using in previous exercises and cast each obstacle into a Shapely Polygon() object. You'll then generate a random bunch of points and test each one for collision with obstacle polygons. Think about what the best approach might be when it comes to testing points for collision. Do you need to test all points against all polygons?

Good luck! And for a peek at our solution you can scroll down to the link at the bottom of the notebook.